package a00_LeetCode.Tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @Author quan
 * @Description 左叶子值之和
 * 左叶子：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
 * @Date 2023/3/31 15:18
 */
public class Num404_sumOfLeftLeaves {
    /**
     * 递归法
     */
//    判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
//如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。后序遍历
   /* public int sumOfLeftLeaves(TreeNode root) {
        //空树
        if(root == null){
            return 0;
        }
        //如果碰见的是叶子节点
        if(root.left == null && root.right == null){
            return 0;
        }
        int leftValue = sumOfLeftLeaves(root.left); //左
        //一定有左叶子存在
        if(root.left != null && root.left.left == null && root.left.right == null){
            leftValue =  root.left.val;
        }
        int rightValue = sumOfLeftLeaves(root.right);  //右
        int sum = leftValue + rightValue;  //中
        return sum;
    }*/
    /**
     * 迭代法:栈实现：加一个result记录值
     */
   /* public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        int result = 0;
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null && node.left.left==null && node.left.right == null){
                result = result+ node.left.val;
            }
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        return result;
    }*/
    /**
     * 方法3：层序遍历实现:加一个result记录值
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        int result = 0;
        while (!deque.isEmpty()){
            TreeNode node = deque.pop();
            if(node.left != null){
                deque.offer(node.left);
                if(node.left != null && node.left.left == null && node.left.right == null){
                    result += node.left.val;
                }
            }
            if(node.right != null){
                deque.offer(node.right);
            }
        }
        return result;
    }
}
